package com.shopee;

import java.util.HashMap;

/**
 * Lru 缓存
 * 思路 利用 hash + 双向链表
 *
 */
public class LRU {

    /**
     * 头指针 最久未使用的数据
     */
    private Node head = null ;

    /**
     * 尾指针 最近一次使用的数据
     */
    private Node tail = null ;

    /**
     * 长度
     */
    private int length ;

    private volatile int curLength = 0 ;

    private HashMap<String,Node> hashMap = new HashMap<>() ;

    public LRU(int length) {
        this.head = new Node();
        this.tail = new Node();
        this.length = length;
        head.next = tail ;
        tail.pre = head ;
    }


    public static void main(String[] args) {
        LRU lru = new LRU(5);
        for (int i = 1; i < 10; i++) {
            lru.insertData("i"+i , i );
        }
        lru.print();
        System.out.println(lru.get("i8"));
        lru.print();
        lru.insertData("i20",20);
        lru.print();
    }

    public void print(){

        int count = 50 ;
        Node temp = tail ;
        while (temp.pre.pre != null && count >0 ){
            System.out.print(temp.pre.data + "\t");
            count -- ;
            temp = temp.pre ;
        }
        System.out.println();
    }
    /// 头插法
    public void insertData(String key , int data){
        Node temp = new Node(key,data);
        hashMap.put(key,temp);
        if (curLength < length){
            // 未达到空间上线 放入  1 --> 3
            curLength++ ;
        }else {
            // 已经达到空间上限  需要删除 head节点 再插入
            head.next = head.next.next ;
            head.next.pre = head ;
        }
        // 将新节点插入到tail部位
        tail.pre.next = temp ;
        temp.pre = tail.pre ;
        temp.next = tail ;
        tail.pre = temp ;
    }

    public int get(String key){
        if (hashMap.get(key) != null ){
            // adjust the order
            Node node = hashMap.get(key);
            if (node.next.next == null){
                // 此节点已经是常使用的一个了
                return node.data ;
            }

            node.pre.next = node.next ;
            node.next.pre = node.pre ;

            tail.pre.next = node ;
            node.pre = tail.pre ;
            node.next = tail ;
            tail.pre = node ;
            //hashMap.put(key,node);
            return node.data ;
        }
        return -1 ;
    }

    static class Node{

        public String key ;
        public Integer data ;

        public Node pre ;

        public Node next ;

        public Node(String key, int data){
            this.key = key ;
            this.data = data  ;
        }

        public Node(){

        }

    }
}
